package z;

import java.util.LinkedList;

/**
 * @author fangkun
 * @create 2023-01-09-10:33
 *
 * 单调队列应用：
 *
 * 给定一个整型数组arr，和一个整数num
 * 某个arr中的子数组sub，如果想达标，必须满足: sub中最大值 - sub中最小值 <= num
 * 返回arr中达标子数组的数量
 *
 * 如果子数组arr[L...R]达标，向两端延伸L、R的子数组也达标
 * 如果子数组arr[L...R]不达标，向两端延伸L、R的子数组也不达标
 */
public class subArrayNum {

    public static int getNum(int[] arr, int num){
        //判空
        if(arr == null || arr.length == 0){
            return 0;
        }

        //单调队列
        LinkedList<Integer> qmin = new LinkedList<>();
        LinkedList<Integer> qmax = new LinkedList<>();

        int L = 0;
        int R = 0;
        int res = 0;
        while (L < arr.length){

            while (R < arr.length){
                while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]){
                    qmin.pollLast();
                }
                qmin.addLast(R);

                while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]){
                    qmax.pollLast();
                }
                qmax.addLast(R);

                if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num){
                    break;
                }
                //R是第一个违规的位置
                R++;
            }

            res += R - L;

            if (qmin.peekFirst() == L){
                qmin.pollFirst();
            }
            if (qmax.peekFirst() == L){
                qmax.pollFirst();
            }
            L++;
        }
        return res;
    }

    public static void main(String[] args) {

    }
}
